package com.peng.leetcode.unionFind;

import java.util.HashMap;
import java.util.Map;

/**
 * RemoveStones
 * <p>
 * 947. 移除最多的同行或同列石头
 * <p>
 * n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
 * <p>
 * 如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
 * <p>
 * 给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
 * <p>
 * 链接：https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column
 *
 * @author: lupeng6
 * @create: 2021/1/15 11:33
 */
public class RemoveStones {

    public static void main(String[] args) {
        int[][] stones = {{0, 0}, {0, 2}, {1, 1}, {2, 0}, {2, 2}};
        new RemoveStones().removeStones(stones);
    }


    public int removeStones(int[][] stones) {
        if (stones == null || stones.length == 0) {
            return 0;
        }
        UnionFind unionFind = new UnionFind();
        for (int i = 0; i < stones.length; i++) {
            int[] stone = stones[i];
            int x = stone[0];
            int y = stone[1];
            int xx = 20000 + x;
            unionFind.union(xx, y);
        }
        return stones.length - unionFind.getCount();
    }


    private static class UnionFind {
        Map<Integer, Integer> parent = new HashMap<>();
        int count = 0;

        public int find(int x) {
            if (!parent.containsKey(x)) {
                parent.put(x, x);
                count++;
            }

            if (parent.get(x) != x) {
                parent.put(x, find(parent.get(x)));
                x = parent.get(x);
            }
            return x;
        }

        public void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            if (xRoot != yRoot) {
                parent.put(xRoot, yRoot);
                count--;
            }
        }

        public int getCount() {
            return this.count;
        }
    }

}
